Nowadays, with the development of network communication and electronic commerce, security ensuring in communication has become an important issue. One method for ensuring security is cryptographic technology, and communication using various encryption techniques is currently done in actuality.
For example, a system has been put into practical use, in which a cryptographic processing module is embedded in a compact device such as an IC card, and in which data transmission and reception is performed between the IC card and a reader/writer serving as a data reading and writing apparatus, thereby performing an authentication process or encryption and decryption of transmitted and received data.
There are various cryptographic processing algorithms, which are broadly classified into a public-key cryptographic scheme in which an encryption key and a decryption key are set as different keys, for example, a public key and a secret key, and a common-key cryptographic scheme in which an encryption key and a decryption key are set as a common key.
The common key cryptographic scheme has various algorithms. One of them is a scheme in which a plurality of keys are generated on the basis of a common key, and in which a data transformation process in units of blocks (such as 64-bit or 128-bit) is repeatedly performed using the plurality of generated keys. A typical algorithm to which such a key generation scheme and a data transformation process are applied is a common-key block-cipher scheme.
As a typical common-key block-cipher algorithm, for example, a DES (Data Encryption Standard) algorithm, which is a U.S. standard cryptography, is broadly used in various fields.
The common-key block-cipher algorithm, typified by the DES, can be mainly divided into round-function sections that perform transformation of input data, and a key scheduling section that generates round keys applied in respective rounds of the round-function (F-function) sections. Round keys (sub-keys) that are to be applied in the respective rounds of the round-function sections are generated on the basis of one master key (a main key) that is input to the key scheduling section, and are applied in the respective round-function sections.
A Feistel structure has been known as a specific structure for executing an algorithm to which such round functions are applied. The Feistel structure has a structure that transforms plaintext into ciphertext by simply repeating transformation functions which are called round functions. Examples of documents describing cryptographic processes to which Feistel structures are applied include Non-Patent Document 1 and Non-Patent Document 2.
However, for example, a common-key cryptographic process to which a Feistel structure is applied has a problem of leakage of keys due to cryptanalysis. Differential analysis (also called differential cryptanalysis or differential attack), in which keys applied in respective round functions are analyzed by analyzing multiple pieces of input data (plaintext) having a certain difference and pieces of output data (ciphertext) for the input data, and linear analysis (also called linear cryptanalysis or linear attack), in which analysis based on plaintext and corresponding ciphertext is performed, have been known as typical techniques of cryptanalysis or attack techniques.
Easy analysis of keys due to cryptanalysis implies low security of a cryptographic process using the keys. In cryptographic algorithms of the prior art, because processes (transformation matrices) that are applied in linear transformation sections of round-function (F-function) sections are equal to one another in rounds of respective stages, analysis is feasible, resulting in easy analysis of keys.
As a configuration for dealing with such a problem, a configuration has been proposed, in which two or more different matrices are arranged in linear transformation sections of round-function (F-function) sections in a Feistel structure. This technique is called a diffusion-matrix switching mechanism (DSM: Diffusion Switching Mechanism, hereinafter, referred to as “DSM”). Resistance to differential attacks or linear attacks can be enhanced using this DSM.
The diffusion-matrix switching mechanism (DSM) is provided as a configuration that can be applied to a typical Feistel structure having two data lines. In contrast, there is an extended-type Feistel structure having three or more data lines, which is different from the typical Feistel structure having two data lines. However, no configuration has been disclosed, in which the above-mentioned diffusion-matrix switching mechanism (DSM) is applied in such an extended-type Feistel structure having three or more data lines so that resistance to differential attacks or linear attacks is enhanced.
Non-Patent Document 1: K. Nyberg, “Extended Feistel structures”, ASIACRYPT'96, SpringerVerlag, 1996, pp. 91-104.
Non-Patent Document 2: Yuliang Zheng, Tsutomu Matsumoto, Hideki Imai: On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses. CRYPTO 1989: 461-480